#ifndef SORT_H_
#define SORT_H_
#include<vector>
using namespace std;

template<typename type>
void insertSort(type *array, int num) {
	type tmp;
	for (int i = 1,j = 0; i < num; ++i) {
		tmp = array[i];
		for (j = i - 1; j >= 0; --j)
			if (array[j] > tmp)
				array[j + 1] = array[j];
			else
				break;

		array[j + 1] = tmp;
	}
}

template<typename type>
void shellSort(type *array, int num) {
	vector<int> increSerial = { 1,5,19 };
	for (int k = increSerial.size() - 1; k >= 0; --k) {
		int increment = increSerial.at(k);
		for (int i = increment; i < num; ++i) {
			type tmp = array[i];
			int j;
			for (j = i; j >= increment; j -= increment) {
				if (array[j - increment] > tmp)
					array[j] = array[j - increment];
				else
					break;
			}
			array[j] = tmp;
		}
	}
}

template<typename type>
void heapSort(type *array, int num) {
	for (int i = 1; i < num; ++i) {
		int child = i;
		type tmp = array[child];
		for (int parent = (child + 1) / 2 - 1; parent >= 0; parent = (child + 1) / 2 - 1) {
			if (array[parent] < tmp)
				array[child] = array[parent];
			else
				break;
			child = parent;
		}
		array[child] = tmp;
	}
}

template<typename type>
void mergeSort(type *array, int num) {
	type *tmpArray = new type[num];
	if (tmpArray == nullptr) {
		cout << "Failed to allocate memory!!!,mergesort failed!";
		return;
	}
	Msort<type>(array, tmpArray, 0, num - 1);
	delete tmpArray;
}

template<typename type>
void Msort(type *array, type *tmpArray, int begin, int end) {
	int centre;
	if (begin < end) {
		centre = (begin + end) / 2;
		Msort<type>(array, tmpArray, begin, centre);
		Msort<type>(array, tmpArray, centre + 1, end);
		Merge<type>(array, tmpArray, begin, centre + 1, end);
	}
}

template<typename type>
void Merge(type *array, type *tmpArray, int Lbegin, int Rbegin, int Rend) {
	int Lpos = Lbegin;
	int Lend = Rbegin - 1;
	int tmpbegin = Lbegin;
	while (Lbegin <= Lend && Rbegin <= Rend) {
		if (array[Lbegin] < array[Rbegin])
			tmpArray[tmpbegin++] = array[Lbegin++];
		else
			tmpArray[tmpbegin++] = array[Rbegin++];
	}
	while (Lbegin <= Lend)
		tmpArray[tmpbegin++] = array[Lbegin++];
	while (Rbegin <= Rend)
		tmpArray[tmpbegin++] = array[Rbegin++];
	tmpbegin = Lpos;
	while (tmpbegin <= Rend)
		array[Lpos++] = tmpArray[tmpbegin++];
}

template<typename type>
void quickSort(type *array, int num) {
	Qsort(array, 0, num - 1);
}

template<typename type>
void Qsort(type *array, int begin, int end) {
	const int cutoff = 5;
	if (begin + cutoff < end) {
		int i = begin, j = end;
		type pivot = getPivot(array, begin, end);
		for (;;) {
			while (array[++i] < pivot);
			while (array[--j] > pivot);
			if (i < j)
				swap(array[i], array[j]);
			else
				break;
		}
		swap(array[i], array[end]);
		Qsort(array, begin, i - 1);
		Qsort(array, i + 1, end);
	}
	else {
		insertSort<type>(array + begin, end - begin + 1);
	}
}

template<typename type>
type getPivot(type *array, int begin, int end) {
	int centre = (begin + end) / 2;
	if (array[centre] < array[begin])
		swap(array[centre], array[begin]);
	if (array[end] < array[begin])
		swap(array[begin], array[end]);
	if (array[centre] < array[end])
		swap(array[centre], array[end]);
	swap(array[centre], array[end]);
	return array[end];
}

#endif